package com.currentbp.Interesting.likou.complete;

import com.currentbp.util.all.StringUtil;
import org.junit.Test;

/**
 * @author baopan
 * @createTime 2024-04-17 09:32:10
 */
public class T0343integerBreak {
    /*
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
     */

    /*
    解题思路2：
    n为总长度，j为最近的一个不可分割长度
    max(n) = Max(max(n-j)*j, (n-j)*j)
    可能情况：最大值= 一个数一分为2的乘积  or   一个区间内的最大值乘以（n-j）的结果

    1: 1
    2: 1+1    max(2-1)*1                                        1
    3: 2+1    max(3-1)*2  max(3-2)*1                             2
    4: 2+2    max(4-1)*3  max(4-2)*2  max(4-3)*1                 4
    5: 2+3    max(5-1)*4  max(5-2)*3  max(5-3)*2  max(5-4)*1     6
    6: 3+3
    7: 3+4=3+2+2
    8: 2+3+3
     */
    @Test
    public void t1() {
        System.out.println(integerBreak(2));
        System.out.println(integerBreak(3));
        System.out.println(integerBreak(4));
        System.out.println(integerBreak(10));
    }

    public int integerBreak(int n) {
        //第i的乘积最大值
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int n1 = 2; n1 <= n; n1++) {
            for (int i = 1; i < n1; i++) {
                int tempMax = Math.max(i * (n1 - i), dp[i] * (n1 - i));
                dp[n1] = Math.max(dp[n1], tempMax);
            }
        }
        StringUtil.printObject(dp);
        return dp[n];
    }

}
